package com.example.rwq_test.niuke.stack;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;

/**
 * 数据流中位数
 *
 * @author renweiqiang
 * @version 1.0.0
 * @createTime 2023/12/12
 */
public class MedianValue {

    /**
     * 二分查找法插入
     */
    private static final List<Integer> LIST = new ArrayList<>();

    public static void insert(int val) {
        if (LIST.isEmpty()) {
            LIST.add(val);
        } else {
            int size = LIST.size() - 1;
            int last = LIST.get(size);
            if (val >= last) {
                LIST.add(val);
            } else {
                int index = getIndex(val, 0, size);
                for (int i = LIST.size() - 1; i > index; i--) {
                    LIST.set(i, LIST.get(i - 1));
                }
                LIST.set(index, val);
                LIST.add(last);
            }
        }
    }

    private static int getIndex(int val, int start, int end) {
        if (start >= end) {
            return start;
        }
        int mid = (start + end) / 2;
        if (val == LIST.get(mid)) {
            return mid;
        }
        if (val > LIST.get(mid)) {
            return getIndex(val, mid + 1, end);
        }
        return getIndex(val, start, mid - 1);
    }

    public static Double getMedian() {
        int i = LIST.size() / 2;
        if (LIST.size() % 2 == 0) {
            return (double) (LIST.get(i - 1) + LIST.get(i)) / 2;
        } else {
            return (double) LIST.get(i);
        }
    }

    public static void main(String[] args) {
        int[] nums = {5,2,3,4,1,6,7,0,8};
        for (int num : nums) {
            insert(num);
            System.out.println(getMedian());
        }
        System.out.println(Arrays.toString(LIST.toArray()));
    }

    /**
     * 利用大头堆和小头堆
     */
    private static final PriorityQueue<Integer> small = new PriorityQueue<>((o1, o2) -> o1.compareTo(o2));
    private static final PriorityQueue<Integer> big = new PriorityQueue<>((o1, o2) -> o2.compareTo(o1));
    private static Boolean flag = true;
    public static void insert1(int val) {
        if (flag) {
            small.offer(val);
            big.offer(small.poll());
            flag = false;
        } else {
            big.offer(val);
            small.offer(big.poll());
            flag = true;
        }
    }

    public static Double getMedian1() {
        if (big.size() == small.size()) {
            return (double) (big.peek() + small.peek()) / 2;
        }
        return (double) big.peek();
    }

    public static void insert2(int val) {
        if (big.isEmpty() || small.isEmpty()) {
            big.offer(val);
        } else {
            Integer pb = big.peek();
            Integer ps = small.peek();
            if (val < pb) {
                big.offer(val);
            } else if (val > ps) {
                small.offer(val);
            } else if (big.size() < small.size()) {
                big.offer(val);
            } else {
                small.offer(val);
            }
        }
        doBalanceQueue();
    }

    public static void doBalanceQueue() {
        if (big.size() > small.size() + 1) {
            small.offer(big.poll());
        } else if (small.size() > big.size() + 1) {
            big.offer(small.poll());
        }
    }

    public static Double getMedian2() {
        if (small.size() == big.size()) {
            return (double) (small.peek() + big.peek()) / 2;
        }
        if (small.size() > big.size()) {
            return (double) small.peek();
        }
        return (double) big.peek();
    }

}
